#include<iostream>
#include<vector>
using namespace std;
/*
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
解体思路：
该题目可以理解为求分隔两个子集的方法，分隔出来的子集left与right有如下规则：
left+right=sum;
left-right=target;
联立两个等式有left=(sum+target)/2
则题目能够转化为求出在目标集合中有几种方法能够填满背包容量为(sum+target)/2的背包
故将题目转化为求0-1背包的问题,但是与0-1背包的递推公式不一样，因为改题目求的是装满背包的所有种方法
假设背包容量为5中此时已经装了重量为1的物品,则装满背包有dp[5-1]种方法，若已经装了2重量，则装满背包有dp[5-2]种方法
依次类推可以得到递推公式有：dp[j]+=dp[j-nums[i]];
*/
int dp(vector<int> nums,int target)
{
    //判断初始条件,若(sum+target)%2==1
    int sum=0;
    for(int i=0;i<nums.size();i++)
        sum+=nums[i];
    if((sum+target)%2==1&&(sum+target)<0)
        return 0;
    //创建dp数组并初始化
    int size = (sum+target)>>1;
    vector<int> dp(size+1);
    //装满容量为0的背包有1种方法
    dp[0] = 1;
    for(int i=0;i<nums.size();i++)
    {
        for(int j=size;j>=nums[i];j--)
        {
            dp[j]+=dp[j-nums[i]];
            //cout<<dp[j]<<" ";
        }
        //cout<<endl;
    }
    return dp[size];
}
int main()
{
    cout<<"enter target:"<<endl;
    int target;
    cin>>target;
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
    {
        cin>>nums[i];
    }
    cout<<dp(nums,target);
    return 0;
}